home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Power Programmierung
/
Power-Programmierung (Tewi)(1994).iso
/
magazine
/
drdobbs
/
1988
/
05
/
holub
/
holub.exm
Wrap
Text File
|
1980-01-01
|
5KB
|
185 lines
#include <ctype.h>
char *factor( str )
char *str;
{
char *expr();
if( isalpha( *str ) ) /* F -> name */
printf( "%c\n", *str );
else if( *str == '(' ) /* F -> ( E ) */
str = expr( ++str );
return ++str;
}
char *term( str )
char *str;
{
str = factor( str ); /* T -> FT' */
while( *str == '*' ) /* T'-> *FT' */
{
str++;
str = factor( str );
printf( "*\n" );
}
return str; /* T'-> eps */
}
char *expr( str )
char *str;
{
str = term( str ); /* E -> TE' */
while( *str == '+' ) /* E'-> +TE' */
{
str++;
str = term( str );
printf( "+\n" );
}
return str; /* E'-> eps */
}
main()
{
char buf[80];
while( gets(buf) )
expr( buf );
}
Example 1: A postfix-output expression compiler
typedef struct node
{
char name[16];
int op;
struct node *left;
struct node *right;
}
NODE;
NODE *new()
{
NODE *p;
void *calloc();
if( !(p = (NODE *) calloc( 1, sizeof(NODE) ) ) )
exit(1);
return p;
}
Example 2: Data structure for constructing syntax trees
NODE *build()
{
char buf[80];
NODE *stack[ 10 ];
NODE **sp = stack - 1;
NODE *p;
while( gets(buf) )
{
switch( *buf )
{
default: p = new();
strcpy( p->name, buf );
*++sp = p;
break;
case '*':
case '+':
p = new();
p->right = *sp-- ;
p->left = *sp-- ;
p->op = *buf ;
p->name[0] = *buf ;
*++sp = p ;
break;
}
}
return *sp--;
}
Example 3: A postfix-to-syntax-tree constructor
trav( root )
struct node *root;
{
static int tnum = 0;
if( !root )
return;
if( !root->op ) /* leaf */
{
printf ( "t%d = %s\n", tnum, root->name );
sprintf( root->name , "t%d", tnum );
++tnum;
}
else
{
trav( root->left );
if( root->left != root->right ) /* Always true */
trav( root->right ); /* unless optimized */
printf("%s %c= %s\n", root->right->name,
root->op, root->left->name );
strcpy( root->name, root->right->name );
}
}
Example 4: A syntax-tree-traversing, code-generation pass
optimize( root )
NODE *root;
{
/* Stupid optimizer to eliminate common subexpressions */
char sig1[ 32 ];
char sig2[ 32 ];
if( root->right && root->left )
{
optimize( root->right );
optimize( root->left );
*sig1 = *sig2 = '\0';
makesig( root->right, sig1 );
makesig( root->left , sig2 );
if( strcmp( sig1, sig2 ) == 0 ) /* subtrees match */
root->right = root->left ;
}
}
makesig( root, str )
NODE *root;
char *str;
{
if( !root )
return;
strcat( str, root->name );
makesig( root->left, str );
makesig( root->right, str );
}
Example 5: A subroutine to do common-subexpression elimination